/*
 * @Author: liusheng
 * @Date: 2022-06-02 11:08:45
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-02 22:48:20
 * @Description: 剑指 Offer II 070. 排序数组中只出现一次的数字
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 剑指 Offer II 070. 排序数组中只出现一次的数字
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

 

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10
 

提示:

1 <= nums.length <= 105
0 <= nums[i] <= 105
 

进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？
 */

#include "header.h"

/*
这种两个两个一对的，数组长度特点，下标也会有特点。什么特点呢？？
1)数组长度一定为奇数，答案也是第奇数个。
因为下标是从0开始的，所以答案下标为偶数。
2)对于答案左边的数，如果nums[i]==nums[i+1],则i一定是偶数
3)对于答案右边的数，如果nums[i]==nums[i+1],则i一定是奇数

那我们该如何使用二分法来判断出答案呢？？
我们可以只拿一边作分析，就拿答案左边的数吧！！！下标分别为奇偶数时的情况。
当下标为偶数时，nums[i]一定等于nums[i+1]
当下标为奇数时，nums[i]一定等于nums[i-1]
所以当满足上面那些条件时，答案一定在右边；否则在左边；
需要注意的则是边界的一些问题
题解补充的小知识点(可以更简洁的解决问题，代码更优美)：
偶数和1异或为 偶数+1
奇数和1异或为 奇数-1
*/
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while (left < right)
        {
            mid = left + (right - left) / 2;
            if (nums[mid] == nums[mid ^ 1])
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }
        
        return nums[left];
    }
};